A conventional data processing system may comprise a processor coupled to a system memory where the processor may comprise one or more levels of cache memory. A cache memory may refer to a relatively small, high-speed memory that contains a copy of information from one or more portions of the system memory. Frequently, the cache memory is physically distinct from the system memory. Such a cache memory may be integral with a processor in the system, commonly referred to as a Level-1 (L1) or primary cache, or may be non-integral with a processor in the system, commonly referred to as a Level-2 (L2) or secondary cache.
When a processor generates a request of an address of data (a read request) and the requested data resides in its cache memory, e.g., L1 cache, then a “cache hit” is said to take place. The processor may then obtain the data from the cache memory without having to access the system memory. If the data is not in the cache memory, then a “cache miss” is said to occur. The memory request may be forwarded to the system memory and the data may subsequently be retrieved from the system memory as would normally be done if the cache did not exist. On a cache miss, the data that is retrieved from the system memory may be provided to the processor and may also be written into the cache memory due to the statistical likelihood that this data will be requested again by that processor. Likewise, if a processor generates a write request, the write data may be written to the cache memory without having to access the system memory over the system bus.
As is known to those skill in the art, a wide variety of cache configurations or organizations are commonly available. For example, a “direct-mapped” cache is organized such that for each addressed location in main memory, there exists one and only one location in a cache data array that could include a copy of such data. In a “n-way set-associative” cache, the cache is configured such that for any one addressed location in main memory, there exists n possible locations within the cache data array that might include a copy of such data.
There have been many methods in designing caches that seek to increase the cache hit rate thereby improving performance of the cache. A “cache hit rate” may refer to the rate at which cache hits occur relative to the total number of accesses that are made to the cache. By improving the cache hit rate, the performance of the system may be improved, i.e., less data needs to be serviced from system memory.
In an “n-way set-associative” cache, one way to improve the performance of the cache is to use a Least Recently Used (LRU) replacement method to assist in determining how data is to be managed in the cache. The LRU replacement method uses a single logical stack construct composed of “n” elements for each of the congruence classes in an n-way set-association cache where each cache entry stores particular data. A congruence class may refer to entries in a way whose addresses are a modulo of one another. As stated above, if an item, e.g., data, requested by the processor is present in the cache, a “cache hit” is said to occur. When a cache hit occurs, the cache entry comprising the information, e.g., data, requested is considered to become the “most recently used” item in its congruence class and is logically moved from its current location in the stack to the top of the stack. The entry in the congruence class that can logically be viewed as being at the bottom of the stack is the “least recently used” item in the congruence class. As stated above, if an item, e.g., data, requested by the processor is not present in the cache, a “cache miss” is said to occur. When a cache miss occurs, the requested item is retrieved from system memory and then stored in the top stack position. When a new entry is inserted in the stack, the cache entry in the bottom stack position of the stack is evicted. The information, e.g., data, at that entry may subsequently be discarded. When there is a cache hit to an entry in the middle of the stack, that entry is moved to the top of the stack. Those entries that are located above the entry requested are each shifted down one position to fill the void left by the entry that moved to the top of the stack.
However, the processor may execute a series of instructions that may only be executed once, such as an interrupt routine. Since these instructions will not be in the cache memory, cache misses will occur. As stated above, in the LRU algorithm, when a cache miss occurs, the requested item is retrieved from system memory and then stored in the top stack position. When a new entry is logically placed at the top of the stack for its congruence class, the cache entry that is logically located at the bottom stack position is evicted. The information, e.g., data, at that entry may subsequently be discarded. When the interrupt routine is completed, the instruction sequence may return to the point of execution prior to the interruption. However, the cache at the point of returning to the prior instruction sequence may contain information that will not be reused (instructions from interrupt routine) and the information that might otherwise have been requested (instructions discarded when the instructions from the interrupt routine were inserted in the stack) has been evicted. Consequently, the cache hit rate may be diminished.
A possible solution to not evicting data that may be requested by the processor once the processor completes a series of instructions that will not reused, e.g., an interrupt routine, is to “pin” the data in the cache. Pinning the data may refer to designating particular data in the cache to not be discarded. That is, pinning the data may refer to designating particular data in the cache to not participate in the LRU algorithm. However, this makes the cache non-transparent to the programmer. That is, the programmer is forced to manage the cache by designating which particular data is to be pinned and which such data is to be unpinned, i.e., when such data is to be available for the LRU algorithm. An alternative approach to pinning data is to define instructions or data that will not be reused as non-cacheable thereby preventing such instructions or data from being stored in the cache. However, this also makes the cache non-transparent to the programmer. That is, the programmer is forced to manage the cache by designating which particular instruction or datum is to be prevented from entering the cache.
Therefore, there is a need in the art for a cache design that does not evict data that may be requested by the processor once the processor completes a series of instructions that will not reused, e.g., an interrupt routine, that is transparent to the programmer.